package com.suanfa.search;

/**
 * Created by buguniao on 16/2/28.
 */
public class BST {
    private class Node{
        private String key;
        private int value;
        private int N;
        private Node left;
        private Node right;

        public Node(String key,int value,int N){
            this.key=key;
            this.value=value;
            this.N=N;
        }
    }
    private Node root;

    public int get(String key){
       return get(root,key);
    }
    private int get(Node x,String key){
        if(x==null){
            return -1;
        }
        int comp = key.compareTo(x.key);
        if(comp<0){
            return get(x.left,key);
        }else if(comp>0){
            return get(x.right,key);
        }else{
            return x.value;
        }
    }
    public void put(String key,int value){
        root=put(root,key,value);
    }
    private Node put(Node x,String key,int value){
        if(x==null){
            return new Node(key,value,1);
        }
        int comp = key.compareTo(x.key);
        if(comp<0){
            x.left=put(x.left,key,value);
        }else if(comp>0){
            x.right=put(x.right,key,value);
        }else{
            x.value=value;
        }
        x.N=size(x);
        return x;
    }
    public int size(Node x){
        if(x==null){
            return 0;
        }
        return size(x.left)+size(x.right)+1;
    }


    public static void main(String[] args){
        BST bst = new BST();
        bst.put("c",30);
        bst.put("a",10);
        bst.put("b",20);
        bst.put("d",40);

        System.out.println(bst.get("d"));
    }
}
